The problem of key management, particularly in broadcast and multicast environments, is well known in the art. Various approaches to solving the problem have been proposed. Generally, the problem relates to distribution of encrypted items and controlling access thereto; to the problem of invalidation (blacklisting) of one or a plurality of receivers which have become compromised; and related issues. Generally, the problem of blacklisting has been considered to be the most difficult part of key management.
The problem to be solved in key management can be presented as follows.
The context is content protection. More specifically, Content Providers distribute their content in some way, e.g. on CD (or DVD) disks. The consumers consume the content using their consumer electronics devices, e.g. such as a personal stereo device. In order to protect the content from being stolen (e.g., illicit copies of it been made) the devices may implement certain restrictions: e.g. a personal stereo device may be required to have no digital outputs. One potential threat is that pirates may manufacture their own versions of the devices, which will not observe these restrictions. In such cases, the goal is to prevent the pirate devices from accessing the content.
One way to achieve the goal is to encrypt all content and to embed all legitimate devices with some secrets, such that they enable these devices to decrypt the content. In fact, this is the venue explored by one of the solutions: so called 4C (proposed by 4 companies: IBM, Intel, Matsushita and Toshiba). One problem that arises in this approach is that the pirates may reverse-engineer some of the legitimate devices and extract the embedded secrets. These secrets may then be used by the pirate devices.
The goal may thus reformulated as follows:
1. The content is distributed in the encrypted form, with K denoting the key used for the encryption (K could be a “key-encrypting-key”)
2. Accompanying the content is a key block B (the key block can be assumed to include “media key”—e.g., the disc's serial number, etc.).
The desired property is:
3. B can be computed (by the content providers, after examining the pirate devices) in such a way that all non-compromised devices can compute K from B, while the pirate devices cannot.
A methodology for computing B (and computing K from B) is provided by a preferred embodiment of the present invention, as described below. For brevity, we refer to this problem as the key distribution problem, KD for short.
Here are some related terms:
Blacklist: the list of devices to which the access to content is to be denied (namely, no blacklisted device can obtain K from B, while all non-blacklisted devices can).
Coalition: the set of legitimate devices reversed-engineered by one pirate group. The secrets extracted from a coalition are used by the respective pirate group to produce their pirate devices. Coalitions are usually assumed to be subsets of the blacklist. However, there might be many pirate groups, each working separately to build their own version of pirate devices.
If all the device of some coalition are blacklisted, then any pirate device constructed using the secrets obtained from these devices is prevented from accessing the content: i.e., it will not be able to compute K from B.
The following publications provide a general background to the field:    R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas, “Multicast Security: A Taxonomy and Efficient Authentication”, IEEE INFOCOM-99, March 1999;    A. Fiat and M. Naor, “Broadcast Encryption”, Crypto-93, 1993;    G. Itkis, “Improved Key Distribution System”, presented at CPTWG, April, 1999, G. Itkis being the inventor of the present invention, a slide presentation accompanying the presentation being available via the Internet at http://www.ndsworld.com/cmp/cmp_docs/mcastcp2.ppt;    D. M. Wallner, E. J. Harder and R. C. Agee, “Key Management for Multicast: Issues and Architectures”, internet draft, 1998, available via the Internet at ftp://ftp.ietf.org/internet-drafts/draft-wallner-key-arclh-01.txt.
The 4C group is said to be working on a solution to the key distribution problem along the lines of the A. Fiat and M. Naor publication, referred to above, but details of their approach have not been made publicly available. It is known that in the A. Fiat and M. Naor approach, also termed herein the Broadcast Encryption (BE) approach, a preset upper bound on the coalition size of blacklisted devices against which the approach protects if they are working together is set, and various parameters such as the key block size depend on the upper bound. Such a scheme typically becomes not secure when a coalition greater in size than the upper bound is formed.
The disclosures of all references mentioned above and throughout the present specification are hereby incorporated herein by reference.